#define infinity (1e9)

int TSP(MGraph graph) {
    int UB, v_lb;
    MinHeap pq;
    Tree u, v;
    Vertex v_idx;

    UB = infinity; /* 初始化上界函数值 */
    pq = (MinHeap)malloc(sizeof(struct BinaryHeapNode));
    InitPQueue(pq, kMaxPQSize); /* 初始化一个空的优先队列pq */
    u = (Tree)malloc(sizeof(struct TreeNode)); /* 创建决策树的根结点 */
    u->idx = 0; /* 起点编号从0开始 */
    u->lb = 0; /* 起点下界为0 */
    u->parent = NULL; /* 根结点没有父结点 */
    u->cnt = 1; /* 当前决策树路径上有1个根结点 */
    Insert(pq, u); /* 将起点入队 */
    while (IsEmpty(pq) == false) {
        u = ExtractMin(pq); /* 最小LB值的结点出列 */
        if (u->lb >= UB) { /* 若当前激活结点的LB值过大 */
            break; /* 跳出循环，结束 */
        }
        if (IsLeaf(graph, u) == true) { /* 若u是决策树中的叶结点 */
            UB = UpdateUB(graph, u,
                          UB); /* 计算u对应的可行解的费用，并更新上界 */
        } else { /* 若u不是叶结点 */
            for (v_idx = 0; v_idx < graph->n_verts; v_idx++) { /* 遍历所有图顶点 */
                /* 若v_idx对应的顶点可以是决策树中u的孩子结点 */
                if (IsNextV(graph, u, v_idx) == true) {
                    v_lb = LB(graph, u, v_idx); /* 计算v的下界函数值 */
                    if (v_lb < UB) { /* 若下界小于上界 */
                        /* 创建u的孩子结点v */
                        v = (Tree)malloc(sizeof(struct TreeNode));
                        v->idx = v_idx;
                        v->lb = v_lb;
                        v->parent = u;
                        v->cnt = u->cnt + 1;
                        Insert(pq, v); /* 将v加入优先队列 */
                    }
                    /* 若下界不小于上界，则剪枝 */
                }
            }
        }
    }
    if (UB == infinity)
        UB = 0; /* 如果根本不存在周游路线，则返回0 */
    return UB;
}